module DGraph (X : sig type vertex end) : 
sig
  type t
  val empty : t
  val add : X.vertex -> (X.vertex list) -> t -> t
  val remove : X.vertex -> t -> t
  val mem : X.vertex -> (X.vertex list) -> t -> bool
  val topologic_sort : t -> t
end = 
struct
  (* We assume that each vertex is different. *)

  exception Not_a_vertex 
  exception Cycle

  type t = (X.vertex * (X.vertex list)) list (* list of (vertex, succ vertex) *)
  
  (* Empty graph *)
  let empty = []
  
  (* Add (vertex,succ) to graph. *)
  let add vertex succ graph = (vertex, succ) :: graph
  
  (* Remove vertex from graph, without regarding if some others point at it. Raise Not_a_vertex if vertex does not appaers in graph. *)
  let remove vertex graph =
    let rec loop = function
      | [] -> raise Not_a_vertex
      | (v,succ) :: t when v = vertex -> t
      | h :: t -> h :: (loop t)
    in loop graph
  
  (* Return true if and only if (vertex,succ) appears in graph. *)
  let mem vertex succ graph =
    try
      let temp_succ = List.assoc vertex graph in
      (* compare if two lists, viewed as sets, are equal *)
      List.for_all (fun x -> List.mem x temp_succ) succ
      && List.for_all (fun x -> List.mem x succ) temp_succ
    with Not_found -> false

  (* Retur true if and only if vertex has some previous vertex in the directed graph graph. *)
  let has_prev vertex graph =
    List.exists (fun (_,list) -> List.mem vertex list) graph
  
  (* Applied a topologic sort to graph. Raise Cycle if graph is not a dag. *)
  let topologic_sort graph =
    let rec loop graph = 
      if graph = [] then []
      else
	let (vertex,succ) = List.find (fun (x,_) -> not (has_prev x graph)) graph in
	loop (remove vertex graph)
    in try loop graph with Not_found -> raise Cycle
end
